class Solution {
private:
    unordered_map<int, vector<string>> ans;
    unordered_set<string> hash;

public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        hash = unordered_set(wordDict.begin(), wordDict.end());
        int n = s.size();
        backtrack(s, 0, n);
        return ans[0];
    }

    void backtrack(const string& s, int i, int& n)
    {
        if (!ans.count(i))
        {
            if (i == n)
            {
                ans[i] = {""};
                return;
            }
            ans[i] = {};
            for (int j = i + 1; j <= n; ++j)
            {
                string word = s.substr(i, j - i);
                if (hash.count(word))
                {
                    backtrack(s, j, n);
                    for (auto& succ : ans[j])
                    {
                        ans[i].push_back(succ.empty() ? word : word + " " + succ);
                    }
                }
            }
        }
    }
};